﻿#pragma once
#include "stdafx.h"

/*
25. K 个一组翻转链表  困难
给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

 

 示例：

 给你这个链表：1->2->3->4->5

 当 k = 2 时，应当返回: 2->1->4->3->5

 当 k = 3 时，应当返回: 3->2->1->4->5

  

  说明：

  你的算法只能使用常数的额外空间。
  你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

  来源：力扣（LeetCode）
  链接：https://leetcode-cn.com/problems/reverse-nodes-in-k-group
  著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

  解题思路：这个题目相当于24题的提高篇吧，如果是给定的数去做翻转，可以写对应的方案，这个题目是是k来
  决定的，所以要写一个通用的做法，我的想法可能很简单，使用栈，多少个就初始化栈空间，通过入栈与出栈来,
  最后判断栈数量是否为为k不满就不改变。
  从新变换。时间复杂度是0（n），空间复杂度是0(k).

*/

struct ListNode {
	int val;
	ListNode *next;
	ListNode() : val(0), next(nullptr) {}
	ListNode(int x) : val(x), next(nullptr) {}
	ListNode(int x, ListNode *next) : val(x), next(next) {}

};

ListNode* reverseKGroup(ListNode* head, int k) {
	  if (k<=1 || head == NULL)
	  {
		  return head;
	  }
	  stack<ListNode *> nodeStack;
	  ListNode* nowHead = new ListNode();
	  nowHead->next = head;
	  ListNode* currentNode = head;
	  ListNode * newhead = nowHead;
	  while (currentNode)
	  {
		  nodeStack.push(currentNode);
		  currentNode = currentNode->next;
		  if (nodeStack.size() == k)
		  {
			  while (nodeStack.size())
			  {
				  newhead->next = nodeStack.top();
				  nodeStack.pop(); //褪栈
				  newhead = newhead->next;
			  }
			  newhead->next = currentNode;
		  }
	  }
	  return nowHead->next;
}

/*
题目解法，可行。
*/